// https://www.lintcode.com/problem/binary-tree-postorder-traversal-null/

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        // write your code here
        List<Integer> ret = new ArrayList<>();
        if (root != null) {
            Stack<TreeNode> s1 = new Stack<>(), s2 = new Stack<>();
            s1.push(root);
            while (!s1.empty()) {
                TreeNode node = s1.pop();
                s2.push(node);
                if (node.left != null) {
                    s1.push(node.left);
                }
                if (node.right != null) {
                    s1.push(node.right);
                }
            }
            while (!s2.empty()) {
                ret.add(s2.pop().val);
            }
        }
        return ret;
    }
}